package com.c2b.algorithm.leetcode.base.backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/combinations/description/'>组合(Combinations)</a>
 * <p>给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。</p>
 * <p>你可以按 任何顺序 返回答案。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 4, k = 2
 *      输出：
 *      [
 *        [2,4],
 *        [3,4],
 *        [2,3],
 *        [1,2],
 *        [1,3],
 *        [1,4],
 *      ]
 *
 * 示例 2：
 *      输入：n = 1, k = 1
 *      输出：[[1]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 20</li>
 *         <li>1 <= k <= n</li>
 *         <li>1 <= m, n <= 300</li>
 *         <li>grid[i][j] 的值为 '0' 或 '1'</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/26 16:03
 */
public class LC0077Combinations_M {
    static class Solution {

        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> retList = new ArrayList<>();
            if (k <= 0 || n < k) {
                return retList;
            }
            getCombine(n, k, 1, new ArrayDeque<>(k), retList);
            return retList;
        }

        private <E> void getCombine(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> retList) {
            // 递归终止条件是：path 的长度等于 k
            if (k == 0) {
                retList.add(new ArrayList<>(path));
                return;
            }
            // 遍历可能的搜索起点
            for (int i = begin; i <= n - k + 1; i++) {
                path.add(i);
                // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
                //System.out.println("递归之前 => " + path);
                getCombine(n, k - 1, i + 1, path, retList);
                //System.out.println("递归之后 => " + path);
                // ==>深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
                path.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> combine = solution.combine(4, 2);
        for (List<Integer> list : combine) {
            for (Integer integer : list) {
                System.out.print(integer + "  ");
            }
            System.out.println();
        }
    }
}
